Sort an array [Merge Sort, Quick Sort]

Time: O(NlogN); Space: O(N); medium

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]

Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]

Output: [0,0,1,1,2,5]

Constraints:

• 1 <= len(nums) <= 50000

• -50000 <= nums[i] <= 50000

1. Merge sort solution

class Solution1(object):
    """
    Time:  O(nlogn)
    Space: O(n)
    """
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def mergeSort(start, end, nums):
            if end - start <= 1:
                return

            mid = start + (end - start) // 2
            mergeSort(start, mid, nums)
            mergeSort(mid, end,  nums)

            right = mid
            tmp = []

            for left in range(start, mid):
                while right < end and nums[right] < nums[left]:
                    tmp.append(nums[right])
                    right += 1
                tmp.append(nums[left])

            nums[start:start+len(tmp)] = tmp

        mergeSort(0, len(nums), nums)

        return nums

s = Solution1()
nums = [5,2,3,1]
assert s.sortArray(nums) == [1,2,3,5]

nums = [5,1,1,2,0,0]
assert s.sortArray(nums) == [0,0,1,1,2,5]

2. Quick sort solution

import random

class Solution2(object):
    """
    Time:  O(nlogn), on average
    Space: O(logn)
    """
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def kthElement(nums, left, k, right, compare):
            def PartitionAroundPivot(left, right, pivot_idx, nums, compare):

                new_pivot_idx = left
                nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

                for i in range(left, right):
                    if compare(nums[i], nums[right]):
                        nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
                        new_pivot_idx += 1

                nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
                return new_pivot_idx

            right -= 1
            while left <= right:
                pivot_idx = random.randint(left, right)
                new_pivot_idx = PartitionAroundPivot(left, right, pivot_idx, nums, compare)
                if new_pivot_idx == k:
                    return
                elif new_pivot_idx > k:
                    right = new_pivot_idx - 1
                else:  # new_pivot_idx < k.
                    left = new_pivot_idx + 1

        def quickSort(start, end, nums):
            if end - start <= 1:
                return
            mid = start + (end - start) // 2
            kthElement(nums, start, mid, end, lambda a, b: a < b)
            quickSort(start, mid, nums)
            quickSort(mid, end, nums)

        quickSort(0, len(nums), nums)
        return nums

s = Solution2()
nums = [5,2,3,1]
assert s.sortArray(nums) == [1,2,3,5]

nums = [5,1,1,2,0,0]
assert s.sortArray(nums) == [0,0,1,1,2,5]

See also:

https://leetcode.com/problems/sort-an-array